#include<stdio.h>
#include<stdlib.h>
#define MAXN 100
int MGraph[MAXN][MAXN];
int visited[MAXN] = {0};
int Nv, Ne;
typedef int Vertex;

void DFS(Vertex v)
{
    visited[v] = 1;
    printf("%d ", v);
    for(int j=0;j<Nv;j++)
    {
        if(MGraph[v][j] && !visited[j])
            DFS(j);
    }
}

void BFS(Vertex v)
{
    int queue[MAXN];
    int first, rear;
    first = rear = -1;
    queue[++rear] = v;
    visited[v] = 1;
    while(first < rear)
    {
        int de = queue[++first];
        printf("%d ", de);
        for(int j=0;j<Nv;j++)
        {
            if(MGraph[de][j] && !visited[j])
            {
                queue[++rear] = j;
                visited[j] = 1;
            }
        }
    }
}

void Initial()
{
    for(int i=0;i<MAXN;i++)
        visited[i] = 0;
}

int main()
{
    
    scanf("%d%d", &Nv, &Ne);
    for(int i=0;i<Nv;i++)
        for(int j=0;j<Nv;j++)
            MGraph[i][j] = 0;
    for(int i=0;i<Ne;i++)
    {
        int v1, v2;
        scanf("%d%d", &v1, &v2);
        MGraph[v1][v2] = MGraph[v2][v1] = 1;
    }
    DFS(0); printf("\n"); Initial();
    BFS(0); printf("\n"); Initial();

    int v;
    scanf("%d", &v);
    for(int i=0;i<Nv;i++)
        MGraph[i][v] = MGraph[v][i] = 0;
    DFS(0); printf("\n"); Initial();
    BFS(0); printf("\n"); Initial();
    return 0;
}